#ifndef __CSLIST_H__
#define __CSLIST_H__

template<class T>
class ListOperation
{
public:
	static void Construct(T* t)
	{
		new(t) T();
	}
	static void Construct(T* to,T* from)
	{
		new(to) T(*from);
	}
	static void Destruct(T* t)
	{
		t->~T();
	}
};

struct SListHead
{
	SListHead* Next;
	SListHead* Prec;
};

template<class T,class Mem>
class CSListBase
{
	typedef ListOperation<T> Op;
public:
	class iterator
	{
	public:
		iterator() {mHead=0;}
		explicit iterator(SListHead* head) {mHead=head;}
		iterator(const iterator& iter) {mHead=iter.mHead;}
		iterator& operator=(const iterator& iter) {mHead=iter.mHead;return *this;}
		iterator& operator++() {mHead=mHead->Next;return *this;}
		iterator& operator--() {mHead=mHead->Prec;return *this;}
		bool operator==(const iterator& iter) {return mHead==iter.mHead;}
		bool operator!=(const iterator& iter) {return mHead!=iter.mHead;}
		T& operator*() {return *((T*)(mHead+1));}
		T* operator->() {return (T*)(mHead+1);}
	public:
		SListHead* mHead;
	};
public:
	CSListBase() {Init();}
	~CSListBase() {Clear();}
public:
	void Init() {mHead.Next=&mHead;mHead.Prec=&mHead;mNum=0;}
	void Clear();

	SListHead* Malloc()
	{
		return (SListHead*)Mem::Malloc(sizeof(SListHead)+sizeof(T));
	}
	void Free(SListHead* node)
	{
		Mem::Free((void*)node);
	}
public:
	iterator Begin() {return iterator(mHead.Next);}
	iterator End() {return iterator(&mHead);}
	iterator Insert(iterator iter,T& t);
	iterator Erase(iterator iter);
	

	bool Empty() {return Begin()==End();}
	int GetSize() {return mNum;}
	
	T& Front() {return *((T*)(mHead.Next+1));}
	void PushFront(T& t);
	void PopFront();
	
	T& Back() {return *((T*)(mHead.Prec+1));}
	void PushBack(T& t);
	void PopBack();

	T& operator[](int index);
private:
	SListHead mHead;
	int mNum;
};

template<class T,class Mem>
typename CSListBase<T,Mem>::iterator CSListBase<T,Mem>::Insert(typename CSListBase<T,Mem>::iterator iter,T& t)
{
	SListHead* node = Malloc();
	if(!node)
		return End();
	Op::Construct(((T*)(node+1)),&t);
	SListHead* nextnode = iter.mHead;
	SListHead* prenode = nextnode->Prec;
	node->Next=nextnode;
	nextnode->Prec=node;
	node->Prec=prenode;
	prenode->Next=node;
	mNum++;
	return iterator(node);
}

template<class T,class Mem>
typename CSListBase<T,Mem>::iterator CSListBase<T,Mem>::Erase(typename CSListBase<T,Mem>::iterator iter)
{
	SListHead* nextnode = iter.mHead->Next;
	SListHead* precnode = iter.mHead->Prec;
	nextnode->Prec=precnode;
	precnode->Next=nextnode;
	Op::Destruct((T*)(iter.mHead+1));
	Free(iter.mHead);
	mNum--;
	return iterator(nextnode);
}

template<class T,class Mem>
void CSListBase<T,Mem>::Clear()
{
	while(!Empty())
		PopFront();
	mNum=0;
}

template<class T,class Mem>
void CSListBase<T,Mem>::PushFront(T& t)
{
	Insert(Begin(),t);
}

template<class T,class Mem>
void CSListBase<T,Mem>::PopFront()
{
	if(!Empty())
		Erase(Begin());
}

template<class T,class Mem>
void CSListBase<T,Mem>::PushBack(T& t)
{
	Insert(End(),t);
}

template<class T,class Mem>
void CSListBase<T,Mem>::PopBack()
{
	if(!Empty())
		Erase(iterator(mHead.Prec));
}

template<class T,class Mem>
T& CSListBase<T,Mem>::operator[](int index)
{
	iterator iter=Begin();
	for(int i=0;iter!=End()&&i<index;++iter,++i);
	if(iter==End())
		return *((T*)0);
	return *((T*)(iter.mHead+1));
}


#endif

